package calculation;

import java.util.Arrays;

/**
 * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
 * @author 78044
 */
public class Topic3 {

    /**
     * 自己的解法
     * @param nums
     * @return
     */
    public int[] productExceptSelf1(int[] nums) {
        int[] output = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            System.out.println("--------------------");
            output[i] = 1;
            // 比i小的数的积
            for (int j = 0; j <i ; j++) {
                System.out.println(nums[j]);
                output[i] = output[i]*nums[j];
            }
            System.out.println("++++++++++++++++++++");
            // 比i大的数的积
            for (int j = i+1; j < nums.length; j++) {
                System.out.println(nums[j]);
                output[i] = output[i]*nums[j];
            }
            System.out.println("--------------------");
        }
        System.out.println(Arrays.toString(output));
        return output;
    }

    /**
     * 看官方后的解法
     * 第一个数组的第一个数的前缀之积为1  最后一个数的后缀之积为1
     * 除第一个数外 每个数的前缀之积为其前一个数的前缀之积乘以其前一个数
     * 除最后一个数外 每个数的后缀之积为其后一个数的后缀之积乘以其后一个数
     * 前缀之积乘以后缀 为最后结果
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        // 求前缀之积
        output[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            output[i] = output[i-1]*nums[i-1];
        }
        System.out.println(Arrays.toString(output));
        // 求后缀之积与前缀之积
        int num = 1;
        for (int i = nums.length-2; i >=0; i--) {
            num *= nums[i+1];
            output[i] = output[i]*num;
            System.out.println(output[i]);
        }
        System.out.println(Arrays.toString(output));
        return output;
    }

    public static void main(String[] args) {
        new Topic3().productExceptSelf(new int[]{1,2,3,4});
    }
}
